using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Threading;

using A4G.Core;
using System.Threading.Tasks;

namespace A4G.Core.Algorithms
{
    public class HirschbergAlignment
    {
        private const int minimalMatrixDimension = 4;

        private delegate void AlignSubMatrixDelegate(Rectangle sequenceRectangle, AlignmentScore topLeftScore, AlignmentScore bottomRightScore);

        public HirschbergAlignment(string sequence1, string sequence2, ScoringMatrix scoringMatrix, double gapPenaltyConstant)
            : this(sequence1, sequence2, scoringMatrix, new PolinomialGapMethodProvider(gapPenaltyConstant))
        {
        }

        public HirschbergAlignment(string sequence1, string sequence2, ScoringMatrix scoringMatrix, double[] gapPenaltyConstants)
            : this(sequence1, sequence2, scoringMatrix, new PolinomialGapMethodProvider(gapPenaltyConstants))
        {
        }

        public HirschbergAlignment(string sequence1, string sequence2, ScoringMatrix scoringMatrix, IGapMethodProvider gapMethodProvider)
        {
            if (sequence1.Length <= sequence2.Length)
            {
                _sequence1 = sequence1;
                _sequence2 = sequence2;
            }
            else
            {
                _sequence1 = sequence2;
                _sequence2 = sequence1;
            }

            _scoringMatrix = scoringMatrix;
            _gapMethodProvider = gapMethodProvider;
            _topLevelRectangle = new Rectangle(0, 0, Sequence1.Length - 1, Sequence2.Length - 1);

            _path = new AlignmentPath(Sequence1, Sequence2);
        }

        private readonly string _sequence1;
        public string Sequence1
        {
            get { return _sequence1; }
        }

        private readonly string _sequence2;
        public string Sequence2
        {
            get { return _sequence2; }
        }

        private readonly ScoringMatrix _scoringMatrix;
        public ScoringMatrix ScoringMatrix
        {
            get { return _scoringMatrix; }
        }

        private IGapMethodProvider _gapMethodProvider;
        public IGapMethodProvider GapMethodProvider
        {
            get { return _gapMethodProvider; }
        }

        private readonly Rectangle _topLevelRectangle;
        public Rectangle TopLevelRectangle
        {
            get { return _topLevelRectangle; }
        }

        private bool _aborted = false;
        public bool Aborted
        {
            get { return _aborted; }
            set { _aborted = value; }
        }

        private readonly AlignmentPath _path;
        private AlignmentPath Path
        {
            get { return _path; }
        }

        public AlignmentPath GetAlignmentPath()
        {
            AlignmentScore topLeftScore = new AlignmentScore();
            topLeftScore.SequenceCoordinate.X = -1;
            topLeftScore.SequenceCoordinate.Y = -1;

            AlignmentScore bottomRightScore = new AlignmentScore();
            bottomRightScore.SequenceCoordinate.X = Sequence1.Length - 1;
            bottomRightScore.SequenceCoordinate.Y = Sequence2.Length - 1;

            Path.Clear();
            Path.Add(topLeftScore);

            Task mainTask = AlignSubMatrix(TopLevelRectangle, topLeftScore, bottomRightScore);
            mainTask.Wait();

            Path.RemoveAt(0);
            return Path;
        }

        private Task AlignSubMatrix(Rectangle sequenceRectangle, AlignmentScore topLeftScore, AlignmentScore bottomRightScore)
        {
            return Task.Factory.StartNew(() =>
                InternalAlignSubMatrix(sequenceRectangle, topLeftScore, bottomRightScore),
                TaskCreationOptions.AttachedToParent);
        }

        private void InternalAlignSubMatrix(Rectangle sequenceRectangle, AlignmentScore topLeftScore, AlignmentScore bottomRightScore)
        {
            Trace.WriteLine(string.Format("[{0}] - Rectangle {1}", Thread.CurrentThread.ManagedThreadId, sequenceRectangle.ToString()), "HirschbergAlignmentTraceCategory");

            if (Aborted)
            {
                return;
            }

            int dimI = sequenceRectangle.X2 - sequenceRectangle.X1;
            int dimJ = sequenceRectangle.Y2 - sequenceRectangle.Y1;
            if ((dimI < 0) || (dimJ < 0))
            {
                return;
            }

            if ((dimI < minimalMatrixDimension) || (dimJ < minimalMatrixDimension))
            {
                AlignTerminalRectangle(sequenceRectangle, topLeftScore, bottomRightScore);
                return;
            }

            int I = (sequenceRectangle.X1 + sequenceRectangle.X2) / 2;

            Rectangle upperRectangle = new Rectangle(sequenceRectangle.X1, sequenceRectangle.Y1, I, sequenceRectangle.Y2);
            List<AlignmentScore> upperScores = CalculateAlignmentScores(upperRectangle, topLeftScore);

            Rectangle lowerRectangle = new Rectangle(sequenceRectangle.X2, sequenceRectangle.Y2, I + 1, sequenceRectangle.Y1);
            List<AlignmentScore> lowerScores = CalculateAlignmentScores(lowerRectangle, bottomRightScore);

            lowerScores.Reverse();
            lowerRectangle.Normalize();

            List<AlignmentScore> subPath = CalculateSubPath(
                upperScores.ToArray(),
                lowerScores.ToArray(),
                ref upperRectangle,
                ref lowerRectangle,
                I,
                topLeftScore);

            Path.Splice(topLeftScore, subPath);

            AlignSubMatrix(upperRectangle, topLeftScore, subPath[0]);
            AlignSubMatrix(lowerRectangle, subPath[subPath.Count - 1], bottomRightScore);
        }

        private List<AlignmentScore> CalculateAlignmentScores(Rectangle sequenceRectangle, AlignmentScore topLeftScore)
        {
            int stepX = (sequenceRectangle.X1 <= sequenceRectangle.X2) ? 1 : -1;
            int stepY = (sequenceRectangle.Y1 <= sequenceRectangle.Y2) ? 1 : -1;

            int end_i = sequenceRectangle.X2 + stepX;
            int end_j = sequenceRectangle.Y2 + stepY;

            List<AlignmentScore> scores = new List<AlignmentScore>();
            scores.Add(topLeftScore);

            int y = 0;
            for (int j = sequenceRectangle.Y1; j != end_j; j += stepY, y++)
            {
                Coordinate sequenceCoordinate = new Coordinate(sequenceRectangle.X1 - stepX, j);
                AlignmentScore score = scores[y];
                score.FirstSequenceGapCount = 0;
                score = AlignmentScore.CalculateScore(
                    score,
                    GapMethodProvider,
                    this.ScoringMatrix,
                    AlignmentScore.gapFirstSequence,
                    sequenceCoordinate,
                    Sequence1,
                    Sequence2);
                score.FirstSequenceGapCount = 0;
                scores.Add(score);
            }

            for (int i = sequenceRectangle.X1; i != end_i; i += stepX)
            {
                AlignmentScore prevScore = scores[0];
                Coordinate sequenceCoordinate = new Coordinate(i, sequenceRectangle.Y1 - stepY);
                AlignmentScore score = scores[0];
                score.SecondSequenceGapCount = 0;
                score = AlignmentScore.CalculateScore(
                    score,
                    GapMethodProvider,
                    this.ScoringMatrix,
                    AlignmentScore.gapSecondSequence,
                    sequenceCoordinate,
                    Sequence1,
                    Sequence2);
                score.SecondSequenceGapCount = 0;
                scores[0] = score;

                y = 1;
                for (int j = sequenceRectangle.Y1; j != end_j; j += stepY, y++)
                {
                    AlignmentScore tmp = scores[y];
                    scores[y] = AlignmentScore.CalculateScore(
                        prevScore,
                        scores[y - 1],
                        scores[y],
                        GapMethodProvider,
                        this.ScoringMatrix,
                        new Coordinate(i, j),
                        Sequence1,
                        Sequence2);

                    prevScore = tmp;
                }
            }

            return scores;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="upperScores"></param>
        /// <param name="lowerScores"></param>
        /// <param name="upperRectangle"></param>
        /// <param name="lowerRectangle"></param>
        /// <param name="I"></param>
        /// <param name="topLeftScore"></param>
        /// <returns></returns>
        private List<AlignmentScore> CalculateSubPath(
            AlignmentScore[] upperScores,
            AlignmentScore[] lowerScores,
            ref Rectangle upperRectangle,
            ref Rectangle lowerRectangle,
            int I,
            AlignmentScore topLeftScore)
        {
            int j1 = upperRectangle.Y1;
            int I_upper = I;
            int I_lower = I + 1;
            int J_upper = 0;
            int J_lower = 0;

            AlignmentScore maxScore = new AlignmentScore();
            double maxValue = double.MinValue;
            for (int j_upper = 1; j_upper < upperScores.Length; j_upper++)
            {
                if (j_upper < (upperScores.Length - 1))
                {
                    for (int delta = 0; delta < 2; delta++)
                    {
                        int j_lower = j_upper + delta - 1;
                        double val = upperScores[j_upper].Value + lowerScores[j_lower].Value;
                        if (val > maxValue)
                        {
                            maxValue = val;
                            J_upper = j1 + j_upper - 1;
                            J_lower = j1 + j_lower;

                            int index = (delta == 0) ? AlignmentScore.gapSecondSequence : AlignmentScore.diagonal;
                            maxScore = AlignmentScore.CalculateScore(
                                upperScores[j_upper],
                                GapMethodProvider,
                                this.ScoringMatrix,
                                index,
                                new Coordinate(I_lower, J_lower),
                                Sequence1,
                                Sequence2);
                        }
                    }
                }
            }
            Trace.WriteLine(J_lower.ToString(), "HirschbergAlignmentTraceCategory");

            List<AlignmentScore> subPath = new List<AlignmentScore>();

            Coordinate upperSequenceCoordinate = new Coordinate(I_upper, J_upper);
            Rectangle upperSequenceRectangle = new Rectangle(I_upper, upperRectangle.Y1, I_upper, upperRectangle.Y2);
            AlignmentMatrix upperMatrix = new AlignmentMatrix(upperScores, Sequence1, Sequence2, upperSequenceRectangle, GapMethodProvider, this.ScoringMatrix);
            upperMatrix.Traceback(ref upperSequenceCoordinate, ref subPath);
            upperRectangle.Coordinate2 = upperSequenceCoordinate;

            subPath.Reverse();
            subPath.Add(maxScore);

            Coordinate lowerSequenceCoordinate = new Coordinate(I_lower, J_lower);
            Rectangle lowerSequenceRectangle = new Rectangle(I_lower, lowerRectangle.Y1, I_lower, lowerRectangle.Y2);
            AlignmentMatrix lowerMatrix = new AlignmentMatrix(lowerScores, Sequence1, Sequence2, lowerSequenceRectangle, GapMethodProvider, this.ScoringMatrix);
            lowerMatrix.ReverseTraceback(ref maxScore, ref lowerSequenceCoordinate, ref subPath);
            lowerRectangle.Coordinate1 = lowerSequenceCoordinate;

            TraceWriteSubPath(subPath);
            return subPath;
        }

        private void AlignTerminalRectangle(Rectangle sequenceRectangle, AlignmentScore topLeftScore, AlignmentScore bottomRightScore)
        {
            List<AlignmentScore> subPath = new List<AlignmentScore>();

            Coordinate topLeftStretch = sequenceRectangle.Coordinate1;
            //if ((topLeftScore.SequenceCoordinate.X < 0) && (topLeftScore.SequenceCoordinate.Y < 0))
            //{
            //    topLeftStretch++;
            //}
            //else
            //{
            topLeftStretch.ApplyTracebackPointer(topLeftScore.Pointer, TracebackDirection.TopLeftToBottomRight);
            //}

            Coordinate bottomRightStretch = sequenceRectangle.Coordinate2;
            bottomRightStretch.ApplyTracebackPointer(bottomRightScore.Pointer, TracebackDirection.BottomRightToTopLeft);

            Rectangle stretchRectangle = new Rectangle(topLeftStretch, bottomRightStretch);
            if ((sequenceRectangle.DiffX == 0) && (sequenceRectangle.DiffY != 0) && (Sequence1.Length > 1))
            {
                AlignmentScore lastScore = topLeftScore;
                for (int j = stretchRectangle.Y1; j <= stretchRectangle.Y2; j++)
                {
                    int index = AlignmentScore.gapFirstSequence;
                    lastScore = AlignmentScore.CalculateScore(
                        lastScore,
                        GapMethodProvider,
                        this.ScoringMatrix,
                        index,
                        new Coordinate(stretchRectangle.X1, j),
                        Sequence1,
                        Sequence2);
                    subPath.Add(lastScore);
                }
            }
            else if ((sequenceRectangle.DiffX != 0) && (sequenceRectangle.DiffY == 0) && (Sequence1.Length > 1))
            {
                AlignmentScore lastScore = topLeftScore;
                for (int i = stretchRectangle.X1; i <= stretchRectangle.X2; i++)
                {
                    int index = AlignmentScore.gapSecondSequence;
                    lastScore = AlignmentScore.CalculateScore(
                        lastScore,
                        GapMethodProvider,
                        this.ScoringMatrix,
                        index,
                        new Coordinate(i, stretchRectangle.Y1),
                        Sequence1,
                        Sequence2);
                    subPath.Add(lastScore);
                }
            }
            else
            {
                Coordinate sequenceCoordinate = sequenceRectangle.Coordinate2;
                sequenceCoordinate.ApplyTracebackPointer(bottomRightScore.Pointer, TracebackDirection.BottomRightToTopLeft);
                sequenceCoordinate.Limit(sequenceRectangle);

                Coordinate topLeftCoordinate = sequenceRectangle.Coordinate1;
                if ((topLeftCoordinate.X != 0) && (topLeftCoordinate.Y != 0))
                {
                    topLeftCoordinate++;
                }
                topLeftCoordinate.Limit(sequenceRectangle);

                Rectangle alignmentRectangle = new Rectangle(topLeftCoordinate, sequenceRectangle.Coordinate2);
                AlignmentMatrix matrix = new AlignmentMatrix(Sequence1, Sequence2, alignmentRectangle, GapMethodProvider, this.ScoringMatrix, topLeftScore);
                matrix.Traceback(ref sequenceCoordinate, ref subPath);

                subPath.Reverse();
            }

            Trace.Write("Terminal ", "HirschbergAlignmentTraceCategory");
            TraceWriteSubPath(subPath);
            Path.Splice(topLeftScore, subPath);
        }

        [Conditional("TRACE")]
        private void TraceWriteSubPath(List<AlignmentScore> subPath)
        {
            Trace.WriteLine("subpath:", "HirschbergAlignmentTraceCategory");
            foreach (AlignmentScore score in subPath)
            {
                Trace.WriteLine(score, "HirschbergAlignmentTraceCategory");
            }
        }
    }
}
